package basic.study.wantOffer.chapter3;

/**
 * @ClassName Problem33
 * @Description 二叉搜索树的后续遍历序列
 * @Company inspur
 * @Author Kevin
 * @Date 2020/5/19 17:58
 * @Version 1.0
 */
public class Problem33 {
    class SquenceOfBST {
        public boolean  verifySquenceOfBST(int[] sequence) {
            if (sequence == null || sequence.length <= 0) {
                return false;
            }
            return verifyCore(sequence, 0, sequence.length -1);
        }

        private boolean verifyCore(int[] sequence,int start,int end) {
            if (start >= end) return true;

            //判断左子树
            int mid = start;
            while (sequence[mid] < sequence[end]) {
                mid++;
            }
            //判断右子树
            for (int i = mid; i < end; i++) {
                if (sequence[mid] < sequence[end]) {
                    return false;
                }
            }
            return verifyCore(sequence, start, mid-1) && verifyCore(sequence, mid, end -1);
        }
    }
}
